{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Color Fill LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: floodFill"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #颜色填充"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。</p>\n",
    "\n",
    "<p>待填充的图像用二维数组 <code>image</code> 表示，元素为初始颜色值。初始坐标点的行坐标为 <code>sr</code> 列坐标为 <code>sc</code>。需要填充的新颜色为 <code>newColor</code> 。</p>\n",
    "\n",
    "<p>「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。</p>\n",
    "\n",
    "<p>请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入</strong>：\n",
    "image = [[1,1,1],[1,1,0],[1,0,1]] \n",
    "sr = 1, sc = 1, newColor = 2\n",
    "<strong>输出</strong>：[[2,2,2],[2,2,0],[2,0,1]]\n",
    "<strong>解释</strong>: \n",
    "初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。\n",
    "初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。\n",
    "注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>image</code> 和 <code>image[0]</code> 的长度均在范围 [1, 50] 内。</li>\n",
    "\t<li>初始坐标点 <code>(sr,sc)</code> 满足 <code>0 <= sr < image.length</code> 和 <code>0 <= sc < image[0].length</code> 。</li>\n",
    "\t<li><code>image[i][j]</code> 和 <code>newColor</code> 表示的颜色值在范围 <code>[0, 65535]</code> 内。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [color-fill-lcci](https://leetcode.cn/problems/color-fill-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [color-fill-lcci](https://leetcode.cn/problems/color-fill-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,1,0],[1,0,1]]\\n1\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        basic = image[sr][sc]\n",
    "        def dfs(mp, x, y):\n",
    "            m = len(mp)\n",
    "            n = len(mp[0])\n",
    "            dx = [-1, 1, 0, 0]\n",
    "            dy = [0, 0, 1, -1]\n",
    "    \n",
    "            if x < 0 or x >= m or y < 0 or y >= n or mp[x][y] == newColor or mp[x][y] != basic:\n",
    "                return mp\n",
    "            mp[x][y] = newColor\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                dfs(mp, nx, ny)\n",
    "        dfs(image, sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        def dfs(sr,sc,image):\n",
    "            if 0<=sr<len(image) and 0<=sc<len(image[0]) and image[sr][sc]!=newColor and image[sr][sc]==oldColor:\n",
    "                image[sr][sc]=newColor\n",
    "                dfs(sr+1,sc,image)\n",
    "                dfs(sr-1,sc,image)\n",
    "                dfs(sr,sc+1,image)\n",
    "                dfs(sr,sc-1,image)\n",
    "        oldColor=image[sr][sc] # 需要记录一下原来的颜色是什么\n",
    "        dfs(sr,sc,image)\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[[1,1,1],[1,1,0],[1,0,1]]\n",
    "1\n",
    "1\n",
    "2\n",
    "\n",
    "The length of image and image[0] will be in the range [1, 50].\n",
    "The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.\n",
    "The value of each color in image[i][j] and newColor will be an integer in [0, 65535].\n",
    "\n",
    "Depth-First Search, Breadth-First Search, Array, Matrix\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        dirs = [[0,1],[1,0],[-1,0],[0,-1]]\n",
    "        m, n = len(image), len(image[0])\n",
    "        oldColor = image[sr][sc]\n",
    "        que = deque([[sr, sc]])\n",
    "        while que:\n",
    "            i, j = que.popleft()\n",
    "            if 0 <= i < m and 0 <= j < n and \\\n",
    "                    image[i][j] == oldColor and \\\n",
    "                    image[i][j] != newColor:\n",
    "                image[i][j] = newColor\n",
    "                for dir in dirs:\n",
    "                    que.append([i+dir[0], j+dir[1]])\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        arr = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        m, n = len(image), len(image[0])\n",
    "        visit = [[False]*n for _ in range(m)]\n",
    "        init = image[sr][sc]\n",
    "        que = deque()\n",
    "        que.append([image[sr][sc], sr, sc])\n",
    "        while que:\n",
    "            t, x, y = que.pop()\n",
    "            if t == init:\n",
    "                image[x][y] = newColor\n",
    "                visit[x][y] = True\n",
    "            for a, b in arr:\n",
    "                dx, dy = x+a, y+b\n",
    "                if 0 <= dx < m and 0 <= dy < n and not visit[dx][dy] and image[dx][dy] == init:\n",
    "                    que.append([image[dx][dy], dx, dy])\n",
    "                else:\n",
    "                    continue\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        # 输入：\n",
    "        # image = [[1,1,1],\n",
    "                # [ 1,1,0],\n",
    "                # [ 1,0,1]]\n",
    "        # sr = 1, sc = 1, newColor = 2\n",
    "        # 输出：[[2,2,2],[2,2,0],[2,0,1]]\n",
    "        # 解释:\n",
    "        # 初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。\n",
    "        # 初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。\n",
    "        # 注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。\n",
    "\n",
    "        if image[sr][sc] == newColor: return image\n",
    "        w = len(image)\n",
    "        h = len(image[0])\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        q = []\n",
    "\n",
    "        q.append((sr, sc))\n",
    "        while q:\n",
    "            x, y = q.pop()\n",
    "            old_color = image[x][y]\n",
    "            image[x][y] = newColor\n",
    "            for i in range(4):\n",
    "                nx, ny = x + dx[i], y + dy[i]\n",
    "                if nx < 0 or nx >= w or ny < 0 or ny >= h:\n",
    "                    continue\n",
    "                if image[nx][ny] == old_color and (nx, ny) not in q:\n",
    "                    q.append((nx, ny))\n",
    "\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        q=[(sr,sc)]\n",
    "        visited=set()\n",
    "        change=((-1,0),(1,0),(0,-1),(0,1))\n",
    "        color=image[sr][sc]\n",
    "        while q:\n",
    "            r,c=q.pop(0)\n",
    "            image[r][c]=newColor\n",
    "            visited.add((r,c))\n",
    "            for dx,dy in change:\n",
    "                x,y=r+dx,c+dy\n",
    "                # print(x,y)\n",
    "                if 0<=x<len(image) and 0<=y<len(image[0]) and (x,y) not in visited and image[x][y]==color:\n",
    "                    q.append((x,y))\n",
    "                    # print(q)\n",
    "        return image      \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rows, cols = len(image), len(image[0])\n",
    "        originalColor = image[sr][sc]\n",
    "        if originalColor == newColor: # 颜色已经是我们想要的颜色，直接返回\n",
    "            return image\n",
    "        visited = set()\n",
    "        queue = [(sr, sc)]\n",
    "        directions = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        \n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            image[x][y] = newColor\n",
    "            \n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if 0 <= new_x < rows and 0 <= new_y < cols and (new_x, new_y) not in visited and image[new_x][new_y] == originalColor:\n",
    "                    queue.append((new_x, new_y))\n",
    "                    visited.add((new_x, new_y))\n",
    "                    \n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rowColor = image[sr][sc]\n",
    "        m, n = len(image), len(image[0])\n",
    "        queue = deque[tuple[int, int]]()\n",
    "        queue.append((sr, sc))\n",
    "        while queue:\n",
    "            r, c = queue.popleft()\n",
    "            \n",
    "            if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != rowColor or image[r][c] == newColor:\n",
    "                continue\n",
    "            \n",
    "            image[r][c] = newColor\n",
    "            queue.append((r, c + 1))\n",
    "            queue.append((r, c - 1))\n",
    "            queue.append((r + 1, c))\n",
    "            queue.append((r - 1, c))\n",
    "        \n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        def dfs(sr,sc,image):\n",
    "            if 0<=sr<len(image) and 0<=sc<len(image[0]) and image[sr][sc]!=newColor and image[sr][sc]==oldColor:\n",
    "                image[sr][sc]=newColor\n",
    "                dfs(sr+1,sc,image)\n",
    "                dfs(sr-1,sc,image)\n",
    "                dfs(sr,sc+1,image)\n",
    "                dfs(sr,sc-1,image)\n",
    "        oldColor=image[sr][sc]\n",
    "        dfs(sr,sc,image)\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        old_color = image[sr][sc]\n",
    "        q, head = [[sr, sc]], -1\n",
    "        visited = [[False] * m for _ in range(n)]\n",
    "        visited[sr][sc] = True\n",
    "        image[sr][sc] = newColor\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            x, y = q[head]\n",
    "            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                xx, yy = x + d[0], y + d[1]\n",
    "                if xx < 0 or xx >= n or yy < 0 or yy >= m:\n",
    "                    continue\n",
    "                if visited[xx][yy] or image[xx][yy] != old_color:\n",
    "                    continue\n",
    "                q.append([xx, yy])\n",
    "                visited[xx][yy] = True\n",
    "                image[xx][yy] = newColor\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m, n = len(image), len(image[0])\n",
    "        flag = [[0]*n for _ in range(m)]\n",
    "        color = image[sr][sc]\n",
    "        q = [(sr, sc)]\n",
    "        while q:\n",
    "            r, c = q.pop(0)\n",
    "            image[r][c]=newColor\n",
    "            flag[r][c] = 1\n",
    "            for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                r_ = r + d[0]\n",
    "                c_ = c + d[1]\n",
    "                if 0<=r_<m and 0<=c_<n and image[r_][c_]==color and flag[r_][c_]==0:\n",
    "                    q.append((r_, c_))\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m, n = len(image), len(image[0])\n",
    "        curr_color = image[sr][sc]\n",
    "        if curr_color == newColor:\n",
    "            return image\n",
    "        q = deque()\n",
    "        q.append((sr, sc))\n",
    "        image[sr][sc] = newColor\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for i, j in [(x + 1, y), (x - 1, y), (x , y + 1), (x, y - 1)]:\n",
    "                if 0 <= i < m and 0 <= j < n and image[i][j] == curr_color:\n",
    "                    image[i][j] = newColor\n",
    "                    q.append((i, j))\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        currentColor = image[sr][sc]\n",
    "        if image[sr][sc] == newColor:\n",
    "            return image\n",
    "        queue = deque([(sr, sc)])\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            if image[x][y] == currentColor:\n",
    "                image[x][y] = newColor\n",
    "            dx = [1, 0, -1, 0]\n",
    "            dy = [0, -1, 0, 1]\n",
    "            for i in range(4):\n",
    "                a, b = x + dx[i], y + dy[i]\n",
    "                if 0 <= a < len(image) and 0 <= b < len(image[0]) and image[a][b] == currentColor:\n",
    "                    queue.append((a, b))\n",
    "                    image[a][b] = newColor\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "\n",
    "        target=image[sr][sc]\n",
    "\n",
    "        if target==newColor:\n",
    "            return image\n",
    "        image[sr][sc]=newColor\n",
    "        stack=[[sr,sc]]\n",
    "        row=len(image)\n",
    "        col=len(image[0])\n",
    "\n",
    "        while stack:\n",
    "            x,y=stack.pop()\n",
    "            \n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<row and 0<=y1<col:\n",
    "                    if image[x1][y1]==target:\n",
    "                        stack.append([x1,y1])\n",
    "                        image[x1][y1]=newColor\n",
    "              \n",
    "        \n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, image: List[List[int]], row: int, column: int, oldColor:int, newColor: int) -> None:\n",
    "        if row < 0 or row >= len(image) or column < 0 or column >= len(image[0]):\n",
    "            return\n",
    "        if image[row][column] == newColor:\n",
    "            return\n",
    "        if image[row][column] != oldColor:\n",
    "            return\n",
    "        \n",
    "        image[row][column] = newColor\n",
    "        self.dfs(image, row - 1, column, oldColor, newColor)\n",
    "        self.dfs(image, row + 1, column, oldColor, newColor)\n",
    "        self.dfs(image, row, column - 1, oldColor, newColor)\n",
    "        self.dfs(image, row, column + 1, oldColor, newColor)\n",
    "\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        oldColor = image[sr][sc]\n",
    "        self.dfs(image, sr, sc, oldColor, newColor)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n = len(image),len(image[0])\n",
    "        directions = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        q = deque()\n",
    "        q.append((sr,sc))\n",
    "        vis[sr][sc] = True\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            for dx,dy in directions:\n",
    "                if 0 <= x+dx < m and 0 <= y+dy < n and not vis[x+dx][y+dy] and image[x+dx][y+dy] == image[x][y]:\n",
    "                    q.append((x+dx,y+dy))\n",
    "                    vis[x+dx][y+dy] = True\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j]:\n",
    "                    image[i][j] = newColor\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m, n = len(image), len(image[0])\n",
    "        color = image[sr][sc]\n",
    "        if color == newColor:\n",
    "            return image\n",
    "        q = [(sr, sc)]\n",
    "        while q:\n",
    "            r, c = q.pop(0)\n",
    "            image[r][c]=newColor\n",
    "            for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                r_ = r + d[0]\n",
    "                c_ = c + d[1]\n",
    "                if 0<=r_<m and 0<=c_<n and image[r_][c_]==color:\n",
    "                    q.append((r_, c_))\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        old, new = image[sr][sc], newColor\n",
    "        if old == new: \n",
    "            return image\n",
    "        m, n = len(image), len(image[0])\n",
    "        dirs = [0, -1, 0, 1, 0]\n",
    "        def dfs(image, m, n, x, y):\n",
    "            for i in range(0, 4):\n",
    "                x2, y2 = x + dirs[i], y + dirs[i + 1]\n",
    "                if x2 >= 0 and x2 < m and y2 >= 0 and y2 < n and image[x2][y2] == old:\n",
    "                    image[x2][y2] = new\n",
    "                    dfs(image, m, n, x2, y2)\n",
    "\n",
    "        image[sr][sc] = new\n",
    "        dfs(image, m, n, sr, sc)\n",
    "        return image\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(image,sr,sc,newColor,oldColor):\n",
    "            if sr<0 or sr>=len(image) or sc <0 or sc >= len(image[0]) or image[sr][sc]!=oldColor or newColor == image[sr][sc]:\n",
    "                return\n",
    "            image[sr][sc]=newColor\n",
    "            dfs(image,sr-1,sc,newColor,oldColor)\n",
    "            dfs(image,sr+1,sc,newColor,oldColor)\n",
    "            dfs(image,sr,sc+1,newColor,oldColor)\n",
    "            dfs(image,sr,sc-1,newColor,oldColor)\n",
    "        \n",
    "        dfs(image,sr,sc,newColor,image[sr][sc])\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rows, cols = len(image), len(image[0])\n",
    "        originalColor = image[sr][sc]\n",
    "        if originalColor == newColor: # 颜色已经是我们想要的颜色，直接返回\n",
    "            return image\n",
    "        visited = set()\n",
    "        queue = [(sr, sc)]\n",
    "        directions = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        \n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            image[x][y] = newColor\n",
    "            visited.add((x, y))\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if 0 <= new_x < rows and 0 <= new_y < cols and (new_x, new_y) not in visited and image[new_x][new_y] == originalColor:\n",
    "                    queue.append((new_x, new_y))\n",
    "                    \n",
    "                    \n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        curColor = image[sr][sc]\n",
    "        if curColor == newColor:\n",
    "            return image\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        que = collections.deque([])\n",
    "        que.append((sr,sc))\n",
    "        image[sr][sc] = newColor\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            for tx, ty in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= tx < rows and  0 <= ty < cols and image[tx][ty] == curColor:\n",
    "                    que.append((tx, ty))\n",
    "                    image[tx][ty] = newColor\n",
    "        return image\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n = len(image), len(image[0])\n",
    "        diff = [[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        if image[sr][sc]==newColor:return image\n",
    "        def dfs(i,j):\n",
    "            for x,y in diff:\n",
    "                ix,jy = i+x, j+y\n",
    "                if 0<=ix<m and 0<=jy<n and image[ix][jy]==taget:\n",
    "                    image[ix][jy] = newColor\n",
    "                    dfs(ix,jy)\n",
    "        taget = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef floodFill(self, image, sr, sc, newColor):\n",
    "\t\tm = len(image)\n",
    "\t\tn = len(image[0])\n",
    "\t\told = image[sr][sc]\n",
    "\t\tif old == newColor:\n",
    "\t\t\treturn image\n",
    "\t\timage[sr][sc] = newColor\n",
    "\t\tstack = [[sr, sc]]\n",
    "\t\twhile stack:\n",
    "\t\t\tnxt = []\n",
    "\t\t\tfor x, y in stack:\n",
    "\t\t\t\tfor dx, dy in [[0,1], [1,0], [0,-1], [-1,0]]:\n",
    "\t\t\t\t\tx1 = x + dx\n",
    "\t\t\t\t\ty1 = y + dy\n",
    "\t\t\t\t\tif 0 <= x1 < m and 0 <= y1 < n and image[x1][y1] == old:\n",
    "\t\t\t\t\t\timage[x1][y1] = newColor\n",
    "\t\t\t\t\t\tstack.append([x1, y1])\n",
    "\t\t\tstack = nxt\n",
    "\t\treturn image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        t = set([(sr,sc)])\n",
    "        oldColor = image[sr][sc]\n",
    "        \n",
    "        temp = [(sr,sc)]\n",
    "\n",
    "        while len(temp)>0:\n",
    "            temp2 = []\n",
    "            for e in temp:\n",
    "                if e[0]>0 and image[e[0]-1][e[1]]==oldColor and (e[0]-1, e[1]) not in t:\n",
    "                    temp2.append((e[0]-1, e[1]))\n",
    "                    t.add((e[0]-1, e[1]))\n",
    "                if e[0]<len(image)-1 and image[e[0]+1][e[1]]==oldColor and (e[0]+1, e[1]) not in t:\n",
    "                    temp2.append((e[0]+1, e[1]))\n",
    "                    t.add((e[0]+1, e[1]))\n",
    "                \n",
    "                if e[1]>0 and image[e[0]][e[1]-1]==oldColor and (e[0], e[1]-1) not in t:\n",
    "                    temp2.append((e[0], e[1]-1))\n",
    "                    t.add((e[0], e[1]-1))\n",
    "                if e[1]<len(image[0])-1 and image[e[0]][e[1]+1]==oldColor and (e[0], e[1]+1) not in t:\n",
    "                    temp2.append((e[0], e[1]+1))\n",
    "                    t.add((e[0], e[1]+1))\n",
    "                    \n",
    "            temp = temp2\n",
    "        \n",
    "        for e in t:\n",
    "            image[e[0]][e[1]] = newColor\n",
    "    \n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        # 获取岛屿陆地，再将陆地值均改为2，用深度优先\n",
    "        l = [[1, 0], [-1, 0], [0, 1], [0,-1]]\n",
    "        target = image[sr][sc]\n",
    "        def dfs(x, y):\n",
    "            if image[x][y] != target:\n",
    "                return\n",
    "            else:\n",
    "                image[x][y] = newColor            \n",
    "            for elm in l:\n",
    "                if x+elm[0] in range(len(image)) and y+elm[1] in range(len(image[0])):\n",
    "                    dfs(x+elm[0], y+elm[1])\n",
    "        if target == newColor:\n",
    "            return image\n",
    "        dfs(sr, sc)\n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "    \n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        ori_color = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        sear = [[sr, sc]]\n",
    "        if ori_color == newColor:\n",
    "            return image\n",
    "\n",
    "        def bfs(image, ori_color, sear):\n",
    "            while sear:\n",
    "                [x, y] = sear.pop(0)\n",
    "                for m, n in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):\n",
    "                    if 0 <= m < rows and 0 <= n < cols and image[m][n] == ori_color:\n",
    "                        image[m][n] = newColor\n",
    "                        sear.append([m, n])\n",
    "        bfs(image, ori_color, sear)\n",
    "    \n",
    "        \n",
    "        return image\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        curColor = image[sr][sc]\n",
    "        if curColor == newColor:\n",
    "            return image\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        que = collections.deque([])\n",
    "        que.append((sr,sc))\n",
    "        image[sr][sc] = newColor\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            for tx, ty in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= tx < rows and  0 <= ty < cols and image[tx][ty] == curColor:\n",
    "                    que.append((tx, ty))\n",
    "                    image[tx][ty] = newColor\n",
    "        return image\n",
    "        \"\"\"\n",
    "        curColor = image[sr][sc]\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        def dfs(x, y):\n",
    "            if image[x][y] == curColor:\n",
    "                image[x][y] = newColor\n",
    "            for tx, ty in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= tx < rows and  0 <= ty < cols and image[tx][ty] == curColor:\n",
    "                    dfs(tx, ty)\n",
    "        if curColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        currentColor = image[sr][sc]\n",
    "        if image[sr][sc] == newColor:\n",
    "            return image\n",
    "        image[sr][sc] = newColor\n",
    "        queue = deque([(sr, sc)])\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            dx = [1, 0, -1, 0]\n",
    "            dy = [0, -1, 0, 1]\n",
    "            for i in range(4):\n",
    "                a, b = x + dx[i], y + dy[i]\n",
    "                if 0 <= a < len(image) and 0 <= b < len(image[0]) and image[a][b] == currentColor:\n",
    "                    queue.append((a, b))\n",
    "                    image[a][b] = newColor\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rows, cols = len(image), len(image[0])\n",
    "        originalColor = image[sr][sc]\n",
    "        # if originalColor == newColor: # 颜色已经是我们想要的颜色，直接返回\n",
    "        #     return image\n",
    "        visited = set()\n",
    "        queue = [(sr, sc)]\n",
    "        directions = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        \n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            image[x][y] = newColor\n",
    "            visited.add((x, y))\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if 0 <= new_x < rows and 0 <= new_y < cols and (new_x, new_y) not in visited and image[new_x][new_y] == originalColor:\n",
    "                    queue.append((new_x, new_y))\n",
    "                    \n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "\t\tif image[sr][sc] == newColor:\n",
    "\t\t\treturn image\n",
    "\t\tcurrent_color = image[sr][sc]\n",
    "\t\timage[sr][sc] = newColor\n",
    "\t\tif sr - 1 in range(0, len(image)) and current_color == image[sr - 1][sc]:\n",
    "\t\t\tself.floodFill(image, sr - 1, sc, newColor)\n",
    "\t\tif sr + 1 in range(0, len(image)) and current_color == image[sr + 1][sc]:\n",
    "\t\t\tself.floodFill(image, sr - 1, sc, newColor)\n",
    "\t\tif sc - 1 in range(0, len(image[0])) and current_color == image[sr][sc - 1]:\n",
    "\t\t\tself.floodFill(image, sr, sc - 1, newColor)\n",
    "\t\tif sc + 1 in range(0, len(image[0])) and current_color == image[sr][sc + 1]:\n",
    "\t\t\tself.floodFill(image, sr, sc + 1, newColor)\n",
    "\t\treturn image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        cur_color = image[sr][sc]\n",
    "        if newColor == cur_color: return image\n",
    "        m, n = len(image), len(image[0])\n",
    "        def dfs(x, y):\n",
    "            image[x][y] = newColor\n",
    "            for nx, ny in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == cur_color:\n",
    "                    dfs(nx, ny)\n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        row = len(image)\n",
    "        col = len(image[0])\n",
    "\n",
    "        def draw(r,c):\n",
    "            if 0<= r < row and 0<= c < col and image[r][c] != newColor and image[r][c] == oldColor:\n",
    "                image[r][c] = newColor\n",
    "                draw(r-1,c)\n",
    "                draw(r+1,c)\n",
    "                draw(r,c-1)\n",
    "                draw(r,c+1)\n",
    "        oldColor = image[sr][sc]\n",
    "        draw(sr,sc)\n",
    "        return image "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        currColor = image[sr][sc]\n",
    "        if currColor == newColor:\n",
    "            return image\n",
    "\n",
    "        m=len(image)\n",
    "        n=len(image[0])\n",
    "        stk=[(sr,sc)]\n",
    "        image[sr][sc]=newColor\n",
    "        while stk:\n",
    "            cur = stk.pop(0)\n",
    "            x,y = cur[0],cur[1]       \n",
    "            for nx,ny in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:\n",
    "                if 0<=nx<m and 0<=ny<n and image[nx][ny]==currColor:\n",
    "                    stk.append((nx,ny))\n",
    "                    image[nx][ny]=newColor\n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if image[sr][sc]==newColor:return image\n",
    "        oldColor=image[sr][sc]\n",
    "        def dfs(i,j,newColor):\n",
    "            if not 0<=i<=len(image)-1 or not 0<=j<=len(image[0])-1 or image[i][j]!=oldColor or image[i][j]==newColor:return \n",
    "            image[i][j]=newColor;\n",
    "            dfs(i-1,j,newColor)\n",
    "            dfs(i,j-1,newColor)\n",
    "            dfs(i+1,j,newColor)\n",
    "            dfs(i,j+1,newColor)\n",
    "        dfs(sr,sc,newColor)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "#         orn=image[sr][sc]\n",
    "#         if orn==newColor:return image ###颜色相同，直接返回image\n",
    "#         m,n=len(image),len(image[0])\n",
    "#         # vis=[[0]*n for _ in range(m)]\n",
    "#         def dfs(x,y):\n",
    "#             image[x][y]=newColor\n",
    "#             for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "#                 nx,ny=x+dx,y+dy \n",
    "#                 if 0<=nx<m and 0<=ny<n and image[nx][ny]==orn:\n",
    "#                     dfs(nx,ny)\n",
    "\n",
    "#         dfs(sr,sc)\n",
    "#         return image\n",
    "\n",
    "### 官1：BFS\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        currColor = image[sr][sc]\n",
    "        if currColor == newColor:\n",
    "            return image\n",
    "        \n",
    "        n, m = len(image), len(image[0])\n",
    "        que = collections.deque([(sr, sc)])\n",
    "        image[sr][sc] = newColor\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                    que.append((mx, my))\n",
    "                    image[mx][my] = newColor\n",
    "        \n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        # BFS\n",
    "        curColor = image[sr][sc]\n",
    "        if curColor == newColor:\n",
    "            return image\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        que = collections.deque([])\n",
    "        que.append((sr,sc))\n",
    "        image[sr][sc] = newColor\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            for tx, ty in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= tx < rows and  0 <= ty < cols and image[tx][ty] == curColor:\n",
    "                    que.append((tx, ty))\n",
    "                    image[tx][ty] = newColor\n",
    "        return image\n",
    "        \"\"\"\n",
    "        # DFS\n",
    "        curColor = image[sr][sc]\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "        def dfs(x, y):\n",
    "            if image[x][y] == curColor:\n",
    "                image[x][y] = newColor\n",
    "            for tx, ty in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= tx < rows and  0 <= ty < cols and image[tx][ty] == curColor:\n",
    "                    dfs(tx, ty)\n",
    "        if curColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if newColor==image[sr][sc]:\n",
    "            return image\n",
    "        q = deque([(sr, sc)])\n",
    "        oldColor = image[sr][sc]\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            if r - 1 > -1 and image[r - 1][c] == oldColor:\n",
    "                q.append((r - 1, c))\n",
    "            if r + 1 < len(image) and image[r + 1][c] == oldColor:\n",
    "                q.append((r + 1, c))\n",
    "            if c - 1 > -1 and image[r][c - 1] == oldColor:\n",
    "                q.append((r, c - 1))\n",
    "            if c + 1 < len(image[0]) and image[r][c + 1] == oldColor:\n",
    "                q.append((r, c + 1))\n",
    "            image[r][c] = newColor\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        mask = []\n",
    "        for i in range(len(image)):\n",
    "            mask.append([])\n",
    "            for j in range(len(image[0])):\n",
    "                mask[i].append(image[i][j])\n",
    "        mask[sr][sc] = newColor\n",
    "        return self.process(mask, image, sr, sc, newColor)\n",
    "        \n",
    "    def process(self, mask, image, sr, sc, newColor):\n",
    "        if sr < 0 or sr >= len(image) or sc < 0 or sc >= len(image[0]):\n",
    "            return mask\n",
    "\n",
    "        # left:\n",
    "        if sc > 0 and image[sr][sc] == image[sr][sc - 1] and mask[sr][sc - 1] != newColor:\n",
    "            mask[sr][sc - 1] = newColor\n",
    "            mask = self.process(mask, image, sr, sc - 1, newColor)\n",
    "\n",
    "        # right:\n",
    "        if sc < len(image[0]) - 1 and image[sr][sc] == image[sr][sc + 1] and mask[sr][sc + 1] != newColor:\n",
    "            mask[sr][sc + 1] = newColor\n",
    "            mask = self.process(mask, image, sr, sc + 1, newColor)\n",
    "\n",
    "        # up:\n",
    "        if sr > 0 and image[sr][sc] == image[sr - 1][sc] and mask[sr - 1][sc] != newColor:\n",
    "            mask[sr - 1][sc] = newColor\n",
    "            mask = self.process(mask, image, sr - 1, sc, newColor)\n",
    "\n",
    "        # down:\n",
    "        if sr < len(image) - 1 and image[sr][sc] == image[sr + 1][sc] and mask[sr + 1][sc] != newColor:\n",
    "            mask[sr + 1][sc] = newColor\n",
    "            mask = self.process(mask, image, sr + 1, sc, newColor)\n",
    "\n",
    "        return mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m = image[sr][sc]\n",
    "        def floodFill1(sr,sc):      \n",
    "            if 0 <= sr < len(image) and 0 <= sc < len(image[0]) and image[sr][sc] == m and image[sr][sc] != newColor:\n",
    "                image[sr][sc] = newColor;\n",
    "                floodFill1(sr-1,sc)\n",
    "                floodFill1(sr+1,sc)\n",
    "                floodFill1(sr,sc+1)\n",
    "                floodFill1(sr,sc-1)\n",
    "        floodFill1(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        cur_color = image[sr][sc]\n",
    "        if newColor == cur_color: return image\n",
    "        m, n = len(image), len(image[0])\n",
    "        def dfs(x, y):\n",
    "            image[x][y] = newColor\n",
    "            for nx, ny in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == cur_color:\n",
    "                    dfs(nx, ny)\n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "\n",
    "        def dfs(x, y, color):\n",
    "            if 0 <= x < m and 0 <= y < n:\n",
    "                 if image[x][y] == color and image[x][y] != newColor:\n",
    "                     image[x][y] = newColor\n",
    "                     dfs(x - 1, y, color)\n",
    "                     dfs(x, y - 1, color)\n",
    "                     dfs(x + 1, y, color)\n",
    "                     dfs(x, y + 1, color)\n",
    "        dfs(sr, sc, image[sr][sc])\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        currColor = image[sr][sc]\n",
    "\n",
    "        def dfs(x: int, y: int):\n",
    "            if image[x][y] == currColor:\n",
    "                image[x][y] = newColor\n",
    "                for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                        dfs(mx, my)\n",
    "\n",
    "        if currColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m, n = len(image), len(image[0])\n",
    "        oldColor = image[sr][sc]\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return\n",
    "            if image[i][j] == oldColor:\n",
    "                image[i][j] = newColor\n",
    "                dfs(i-1, j)\n",
    "                dfs(i+1, j)\n",
    "                dfs(i, j-1)\n",
    "                dfs(i, j+1)\n",
    "        if oldColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(\n",
    "        self, \n",
    "        image: List[List[int]], sr: int, sc: int, newColor: int \n",
    "    ) -> List[List[int]]:\n",
    "        tmp = image[sr][sc] \n",
    "        image[sr][sc] = newColor \n",
    "\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "            [1, 0],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for d in dirs:\n",
    "                nextx = x + d[0]\n",
    "                nexty = y + d[1]\n",
    "\n",
    "                if nextx < 0 or nextx > rows-1 or nexty < 0 or nexty > cols-1:\n",
    "                    continue \n",
    "                if visited[nextx][nexty] == False:\n",
    "                    if image[nextx][nexty] == tmp:\n",
    "                        # print(nextx, nexty)\n",
    "                        image[nextx][nexty] = newColor\n",
    "                        visited[nextx][nexty] = True \n",
    "                        dfs(nextx, nexty)\n",
    "\n",
    "        \n",
    "        dfs(sr, sc) \n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n = len(image), len(image[0])\n",
    "        diff = [[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        if image[sr][sc]==newColor:return image\n",
    "        def dfs(i,j):\n",
    "            for x,y in diff:\n",
    "                ix,jy = i+x, j+y\n",
    "                if 0<=ix<m and 0<=jy<n and image[ix][jy]==taget:\n",
    "                    image[ix][jy] = newColor\n",
    "                    dfs(ix,jy)\n",
    "        taget = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n=len(image),len(image[0])\n",
    "        origin,dirctions=image[sr][sc],[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        def dfs(x,y):\n",
    "            image[x][y]=newColor\n",
    "            for i,j in dirctions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and image[new_x][new_y]==origin:\n",
    "                    dfs(new_x,new_y)\n",
    "        if image[sr][sc]==newColor: return image\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# python3 dfs\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rowlen = len(image)\n",
    "        collen = len(image[0])\n",
    "        ref = image[sr][sc]\n",
    "        visited = set()\n",
    "        def dfs(i,j):\n",
    "            if not 0<=i<rowlen or not 0 <=j < collen or image[i][j] != ref or (i,j) in visited:\n",
    "                return\n",
    "            image[i][j] = newColor\n",
    "            visited.add((i,j))\n",
    "            dfs(i-1,j)\n",
    "            dfs(i+1,j)\n",
    "            dfs(i,j-1)\n",
    "            dfs(i,j+1)\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# python3 dfs\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        rowlen = len(image)\n",
    "        collen = len(image[0])\n",
    "        ref = image[sr][sc]\n",
    "        visited = set()\n",
    "        def dfs(i, j):\n",
    "            if not 0 <= i < rowlen or not 0 <= j < collen or image[i][j] != ref or (i, j) in visited:\n",
    "                return\n",
    "            image[i][j] = newColor\n",
    "            visited.add((i, j))\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i, j - 1)\n",
    "            dfs(i, j + 1)\n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(\n",
    "        self, \n",
    "        image: List[List[int]], sr: int, sc: int, newColor: int \n",
    "    ) -> List[List[int]]:\n",
    "        tmp = image[sr][sc] \n",
    "        image[sr][sc] = newColor \n",
    "\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "            [1, 0],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for d in dirs:\n",
    "                nextx = x + d[0]\n",
    "                nexty = y + d[1]\n",
    "\n",
    "                if nextx < 0 or nextx > rows-1 or nexty < 0 or nexty > cols-1:\n",
    "                    continue \n",
    "                if visited[nextx][nexty] == False:\n",
    "                    if image[nextx][nexty] == tmp:\n",
    "                        # print(nextx, nexty)\n",
    "                        image[nextx][nexty] = newColor\n",
    "                        visited[nextx][nexty] = True \n",
    "                        dfs(nextx, nexty)\n",
    "\n",
    "        \n",
    "        dfs(sr, sc) \n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n,m = len(image),len(image[0])\n",
    "        cur_color = image[sr][sc]\n",
    "        def dfs(x,y):\n",
    "            if image[x][y] == cur_color:\n",
    "                image[x][y] = newColor\n",
    "\n",
    "            for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                if 0<=i<n and 0<=j<m and image[i][j] == cur_color:\n",
    "                    dfs(i,j)\n",
    "\n",
    "        if cur_color != newColor:\n",
    "            dfs(sr,sc)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m = image[sr][sc]\n",
    "        def floodFill1(sr,sc):      \n",
    "            if 0 <= sr < len(image) and 0 <= sc < len(image[0]) and image[sr][sc] == m and image[sr][sc] != newColor:\n",
    "                image[sr][sc] = newColor;\n",
    "                floodFill1(sr-1,sc)\n",
    "                floodFill1(sr+1,sc)\n",
    "                floodFill1(sr,sc+1)\n",
    "                floodFill1(sr,sc-1)\n",
    "            else:\n",
    "                return \n",
    "        floodFill1(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        oldColor=image[sr][sc]\n",
    "        def draw(sr, sc):\n",
    "            if 0 <= sr < len(image) and 0 <= sc < len(image[0]) and image[sr][sc] == oldColor and image[sr][sc] != newColor:\n",
    "                image[sr][sc] = newColor\n",
    "                draw(sr+1, sc)\n",
    "                draw(sr-1, sc)\n",
    "                draw(sr, sc+1)\n",
    "                draw(sr, sc-1)\n",
    "        draw(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(\n",
    "        self, \n",
    "        image: List[List[int]], sr: int, sc: int, newColor: int \n",
    "    ) -> List[List[int]]:\n",
    "        tmp = image[sr][sc] \n",
    "        image[sr][sc] = newColor \n",
    "\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "            [1, 0],\n",
    "            [-1, 0]\n",
    "        ]\n",
    "\n",
    "        rows = len(image)\n",
    "        cols = len(image[0])\n",
    "\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for d in dirs:\n",
    "                nextx = x + d[0]\n",
    "                nexty = y + d[1]\n",
    "\n",
    "                if nextx < 0 or nextx > rows-1 or nexty < 0 or nexty > cols-1:\n",
    "                    continue \n",
    "                if visited[nextx][nexty] == False:\n",
    "                    if image[nextx][nexty] == tmp:\n",
    "                        # print(nextx, nexty)\n",
    "                        image[nextx][nexty] = newColor\n",
    "                        visited[nextx][nexty] = True \n",
    "                        dfs(nextx, nexty)\n",
    "\n",
    "        \n",
    "        dfs(sr, sc) \n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        def dfs(y, x, image, newColor, ori, judge):\n",
    "            image[y][x] = newColor\n",
    "            flag = False\n",
    "            if x + 1 < len(image[0]):\n",
    "                if image[y][x + 1] == ori and not judge[y][x + 1]:\n",
    "                    judge[y][x + 1] = True\n",
    "                    flag = True\n",
    "                    dfs(y, x + 1, image, newColor, ori, judge)\n",
    "            if x - 1 >= 0:\n",
    "                if image[y][x - 1] == ori and not judge[y][x - 1]:\n",
    "                    judge[y][x - 1] = True\n",
    "                    flag = True\n",
    "                    dfs(y, x - 1, image, newColor, ori, judge)\n",
    "            if y + 1 < len(image):\n",
    "                if image[y + 1][x] == ori and not judge[y + 1][x]:\n",
    "                    judge[y + 1][x] = True\n",
    "                    flag = True\n",
    "                    dfs(y + 1, x, image, newColor, ori, judge)\n",
    "            if y - 1 >= 0:\n",
    "                if image[y - 1][x] == ori and not judge[y - 1][x]:\n",
    "                    judge[y - 1][x] = True\n",
    "                    flag = True\n",
    "                    dfs(y - 1, x, image, newColor, ori, judge)\n",
    "            if not flag:\n",
    "                return\n",
    "        judge = []\n",
    "        for i in range(len(image)):\n",
    "            judge.append([False] * len(image[0]))\n",
    "        judge[sr][sc] = True\n",
    "        dfs(sr, sc, image, newColor, image[sr][sc], judge)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        start = image[sr][sc]\n",
    "        row = len(image)\n",
    "        col = len(image[0])\n",
    "        jd = [[False for i in range(col)] for j in range(row)]\n",
    "        def dfs(x,y):\n",
    "            nonlocal start, newColor, row, col\n",
    "            if image[x][y] != start:\n",
    "                return\n",
    "            if jd[x][y]:\n",
    "                return\n",
    "            jd[x][y] = True\n",
    "            image[x][y] = newColor\n",
    "            for i, j in direction:\n",
    "                xi = x + i\n",
    "                yi = y + j\n",
    "                if 0<= xi<row and 0<=yi<col:\n",
    "                    dfs(xi,yi)\n",
    "        \n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import sys\n",
    "# sys.setrecursionlimit(10000000)\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        row = len(image)\n",
    "        col = len(image[0])\n",
    "        loc = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        flag = [[0]*col for _ in range(row)]\n",
    "        originColor = image[sr][sc]\n",
    "        def dfs(x,y):\n",
    "            if image[x][y]==originColor:\n",
    "                image[x][y]=newColor\n",
    "            for a,b in loc:\n",
    "                tx,ty = x+a,y+b\n",
    "                if 0<=tx<row and 0<=ty<col and image[tx][ty]==originColor:\n",
    "                    dfs(tx,ty)\n",
    "        if originColor!=newColor:\n",
    "            dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        currColor = image[sr][sc]\n",
    "\n",
    "        def dfs(x: int, y: int):\n",
    "            if image[x][y] == currColor:\n",
    "                image[x][y] = newColor\n",
    "                for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                        dfs(mx, my)\n",
    "\n",
    "        if currColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        currColor = image[sr][sc]\n",
    "\n",
    "        def dfs(x: int, y: int):\n",
    "            if image[x][y] == currColor:\n",
    "                image[x][y] = newColor\n",
    "                for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                        dfs(mx, my)\n",
    "\n",
    "        if currColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n,m=len(image),len(image[0])\n",
    "        oldColor=image[sr][sc]\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            image[x][y]=newColor\n",
    "            DIRS=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "            for dx,dy in DIRS:\n",
    "                newx,newy=x+dx,y+dy\n",
    "                if 0<=newx<n and 0<=newy<m and image[newx][newy]==oldColor:\n",
    "                    dfs(newx,newy)\n",
    "        if oldColor!=newColor:\n",
    "            dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        # 题目意思就是将和起始位置一样颜色的连通块染色\n",
    "        \n",
    "        base_color = image[sr][sc]\n",
    "        m, n = len(image), len(image[0])\n",
    "        \n",
    "        def dfs(x,y):\n",
    "\n",
    "            for tx,ty in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:\n",
    "                if 0<=tx<m and 0<=ty<n and image[tx][ty]==base_color:\n",
    "                    image[tx][ty] = newColor\n",
    "                    dfs(tx, ty)\n",
    "\n",
    "        # 如果一开始就和newColor一样颜色，那就不用dfs染色\n",
    "        if base_color != newColor:      \n",
    "            image[sr][sc] = newColor\n",
    "            dfs(sr, sc)\n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if image[sr][sc]==newColor:\n",
    "            return image\n",
    "        \n",
    "        m, n = len(image), len(image[0])\n",
    "        self.original = image[sr][sc]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            image[x][y] = newColor\n",
    "            if x and image[x-1][y]==self.original:\n",
    "                dfs(x-1, y)\n",
    "            if y and image[x][y-1]==self.original:\n",
    "                dfs(x, y-1)\n",
    "            if x<m-1 and image[x+1][y]==self.original:\n",
    "                dfs(x+1, y)\n",
    "            if y<n-1 and image[x][y+1]==self.original:\n",
    "                dfs(x, y+1)\n",
    "        \n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "### my：DFS\n",
    "# class Solution:\n",
    "#     def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "#         orn=image[sr][sc]\n",
    "#         if orn==newColor:return image ###颜色相同，直接返回image\n",
    "#         m,n=len(image),len(image[0])\n",
    "#         # vis=[[0]*n for _ in range(m)]\n",
    "#         def dfs(x,y):\n",
    "#             image[x][y]=newColor\n",
    "#             for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "#                 nx,ny=x+dx,y+dy \n",
    "#                 if 0<=nx<m and 0<=ny<n and image[nx][ny]==orn:\n",
    "#                     dfs(nx,ny)\n",
    "\n",
    "#         dfs(sr,sc)\n",
    "#         return image\n",
    "\n",
    "# ### 官1：BFS\n",
    "# class Solution:\n",
    "#     def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "#         currColor = image[sr][sc]\n",
    "#         if currColor == newColor:\n",
    "#             return image\n",
    "        \n",
    "#         n, m = len(image), len(image[0])\n",
    "#         que = collections.deque([(sr, sc)])\n",
    "#         image[sr][sc] = newColor\n",
    "#         while que:\n",
    "#             x, y = que.popleft()\n",
    "#             for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "#                 if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "#                     que.append((mx, my))\n",
    "#                     image[mx][my] = newColor\n",
    "        \n",
    "#         return image\n",
    "\n",
    "### 官2：DFS\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        currColor = image[sr][sc]\n",
    "\n",
    "        def dfs(x: int, y: int):\n",
    "            if image[x][y] == currColor:\n",
    "                image[x][y] = newColor\n",
    "                for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                        dfs(mx, my)\n",
    "\n",
    "        if currColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        # 特判\n",
    "        if image[sr][sc] == newColor:\n",
    "            return image\n",
    "        # 感染函数\n",
    "        def infect(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return\n",
    "            if image[i][j] != old:\n",
    "                return\n",
    "            image[i][j] = newColor\n",
    "            for x, y in [(-1, 0), (1,0), (0,-1),(0,1)]:\n",
    "                infect(i+x, j+y)\n",
    "\n",
    "        old = image[sr][sc]\n",
    "        m, n = len(image), len(image[0])\n",
    "        infect(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        color = image[sr][sc]\n",
    "        visited = set()\n",
    "        def dfs(x: int, y: int):\n",
    "            image[x][y] = newColor\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx >= 0 and nx < n and ny >= 0 and ny < m and image[nx][ny] == color and (nx, ny) not in visited:\n",
    "                    visited.add((nx, ny))\n",
    "                    dfs(nx, ny)\n",
    "                    visited.remove((nx, ny))\n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        origin = image[sr][sc]\n",
    "        row, col = len(image), len(image[0])\n",
    "        visted = [[False] * col for i in range(row)]\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < row and 0 <= j < col and not visted[i][j]:\n",
    "                visted[i][j] = True \n",
    "                if image[i][j] == origin:\n",
    "                    image[i][j] = newColor              \n",
    "                    dfs(i + 1, j)\n",
    "                    dfs(i - 1, j)\n",
    "                    dfs(i, j - 1)\n",
    "                    dfs(i, j + 1)\n",
    "        dfs(sr, sc)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n = len(image), len(image[0])\n",
    "        diff = [[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        if image[sr][sc]==newColor:return image\n",
    "        def dfs(i,j):\n",
    "            for x,y in diff:\n",
    "                ix,jy = i+x, j+y\n",
    "                if 0<=ix<m and 0<=jy<n and image[ix][jy]==taget:\n",
    "                    image[ix][jy] = newColor\n",
    "                    dfs(ix,jy)\n",
    "        taget = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m,n=len(image),len(image[0])\n",
    "        origin,dirctions=image[sr][sc],[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        def dfs(x,y):\n",
    "            image[x][y]=newColor\n",
    "            for i,j in dirctions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and image[new_x][new_y]==origin:\n",
    "                    dfs(new_x,new_y)\n",
    "        if image[sr][sc]==newColor: return image\n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        a = len(image)\n",
    "        b = len(image[0])\n",
    "        old_color = image[sr][sc]\n",
    "        if old_color == newColor:\n",
    "            return image\n",
    "        def dfs(i,j,old):\n",
    "            if i < 0 or i >= a or j < 0 or j >= b or image[i][j] != old:\n",
    "                return \n",
    "            image[i][j] = newColor\n",
    "            dfs(i-1,j,old)\n",
    "            dfs(i,j-1,old)\n",
    "            dfs(i+1,j,old)\n",
    "            dfs(i,j+1,old)\n",
    "        dfs(sr,sc,old_color)\n",
    "        return image\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        n, m = len(image), len(image[0])\n",
    "        currColor = image[sr][sc]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if image[x][y] == currColor:\n",
    "                image[x][y] = newColor\n",
    "                for mx, my in ([x+1, y], [x-1, y], [x, y+1], [x, y-1]):\n",
    "                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:\n",
    "                        dfs(mx, my)\n",
    "\n",
    "        if currColor != newColor:\n",
    "            dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        used = [[False] * len(image[0]) for _ in range(len(image))]\n",
    "        def dfs(i, j):\n",
    "            image[i][j] = newColor\n",
    "            used[i][j] = True\n",
    "            for di,dj in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                i2, j2 = i + di, j + dj\n",
    "                if 0 <= i2 < len(image) and 0 <= j2 < len(image[0]) and image[i2][j2] == raw_color and not used[i2][j2]:\n",
    "                    dfs(i2, j2)\n",
    "            \n",
    "            return \n",
    "        \n",
    "        raw_color = image[sr][sc]\n",
    "        dfs(sr, sc)\n",
    "\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        memory = [[0]*len(image[0]) for _ in range(len(image))]\n",
    "        max_x, max_y = len(image), len(image[0])\n",
    "        def all_dir(x, y, target):\n",
    "            if x+1<max_x and memory[x+1][y]==0 and image[x+1][y]==target:\n",
    "                memory[x+1][y] = 1\n",
    "                image[x+1][y] = newColor\n",
    "                all_dir(x+1, y, target)\n",
    "            if x-1>=0 and memory[x-1][y]==0 and image[x-1][y]==target:\n",
    "                memory[x-1][y] = 1\n",
    "                image[x-1][y] = newColor\n",
    "                all_dir(x-1, y, target)\n",
    "            if y+1<max_y and memory[x][y+1]==0 and image[x][y+1]==target:\n",
    "                memory[x][y+1] = 1\n",
    "                image[x][y+1] = newColor\n",
    "                all_dir(x, y+1, target)\n",
    "            if y-1>=0 and memory[x][y-1]==0 and image[x][y-1]==target:\n",
    "                memory[x][y-1] = 1\n",
    "                image[x][y-1] = newColor\n",
    "                all_dir(x, y-1, target)\n",
    "        memory[sr][sc] = 1\n",
    "        target = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        all_dir(sr,sc, target)\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        m = len(image)\n",
    "        if m == 0:\n",
    "            return image\n",
    "        n = len(image[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        dirs = [[0,1], [0,-1], [1,0], [-1,0]]\n",
    "        oldColor = image[sr][sc]\n",
    "        def dfs(sr, sc):\n",
    "            if sr < 0 or sr >= m or sc < 0 or sc >= n:\n",
    "                return \n",
    "            if image[sr][sc] != oldColor:\n",
    "                return\n",
    "            if vis[sr][sc]:\n",
    "                return\n",
    "            vis[sr][sc] = True\n",
    "            image[sr][sc] = newColor\n",
    "            for r, c in dirs:\n",
    "                dfs(sr + r, sc + c)\n",
    "        dfs(sr, sc)\n",
    "        return image\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
